package com.chapter9;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class MyQueue {

	List<Integer> q;
	List<Integer> maxs;
	
	MyQueue(){
		q=new ArrayList<Integer>();
		maxs=new ArrayList<Integer>();
	}
	
	public void enqueue(int val){
		
		if(maxs.isEmpty())
			maxs.add(val);
		while(!maxs.isEmpty() && val>maxs.get(maxs.size()-1))
			maxs.remove(maxs.size()-1);
		maxs.add(val);
		q.add(val);
		return;
	}
	
	public int dequeue(){
		if(q.isEmpty()){
			try{
				throw new Exception();
			}
			catch(Exception e){
				
			}
		}
		if(q.get(0)==maxs.get(0))
			maxs.remove(0);
		return q.remove(0);
	}
	
	public int maxval(){
		if(maxs.isEmpty()){
			try{
				throw new Exception();
			}
			catch(Exception e){
				
			}
		}
		return maxs.get(0);
	}
}
